package problems.contest;

/**
 * 第 103 场双周赛
 * <p>https://leetcode.cn/contest/biweekly-contest-103</p>
 *
 * @author dubulingbo, 2023/04/29, 029 22:28.
 */
public class BCT103 {
    public int maximizeSum(int[] nums, int k) {
        int max = 0;
        for (int num : nums) max = Math.max(num, max);
        return (max + max + k - 1) * k / 2;
    }

    public int[] findThePrefixCommonArray(int[] a, int[] b) {
        int n = a.length;
        boolean[] ea = new boolean[n + 1];
        boolean[] eb = new boolean[n + 1];
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            ea[a[i]] = true;
            eb[b[i]] = true;
            int cnt = 0;
            for (int j = 1; j <= n; ++j) {
                if (ea[j] && eb[j]) {
                    ++cnt;
                }
            }

            ans[i] = cnt;
        }
        return ans;
    }

    int[] dx = {0 , 0, -1, 1};
    int[] dy = {-1, 1, 0, 0};
    public int findMaxFish(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] vis = new boolean[m][n];

        int max = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                max = Math.max(dfs(grid, i, j, vis), max);
            }
        }

        return max;
    }

    private int dfs(int[][] grid, int i, int j, boolean[][] vis) {
        int m = grid.length;
        int n = grid[0].length;
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] < 1 || vis[i][j])
            return 0;

        int ret = grid[i][j];
        vis[i][j] = true;

        for (int d = 0; d < dx.length; ++d) {
            ret += dfs(grid, i + dy[d], j + dx[d], vis);
        }

        return ret;
    }
}
